#ifndef __SGLKLIST_H
#define __SGLKLIST_H

#include <iostream>
#include <fstream>
#include <cassert>
#include <cstdlib>
#include "iofile.h"
using namespace std;

/*
 * The definition of node of single linked list.
 */
template <typename T, typename K>
class _sglklist
{
public:
    K key;
    T *next;
};

/*
 * For single linked list.
 */
template <typename T>
void sglklist_init(T *&head)
{
    head = NULL;
}

template <typename T, typename K>
void sglklist_create(T *&head)
{
    T **p;
    int n;

    sglklist_init(head);
    p = &head;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->next = NULL;
        p = &(*p)->next;
    }
}

template <typename T>
void sglklist_destory(T *&head)
{
    T *p;

    while (head) {
        p = head;
        head = head->next;
        delete p;
    }
}

template <typename T>
void sglklist_print(T *&head)
{
    T *p = head;

    while (p) {
        cout << p->key << " ";
        p = p->next;
    }
    cout << endl;
}

/*
 * For single linked list with cycle.
 */
template <typename T>
void sglklist_init_cycle(T *&head)
{
    head = NULL;
}

template <typename T, typename K>
void sglklist_create_cycle(T *&head)
{
    T **p;
    int n;

    sglklist_init_cycle(head);
    p = &head;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->next = head;
        p = &(*p)->next;
    }
}

template <typename T>
void sglklist_destory_cycle(T *&head)
{
    T *p, *q;

    if (head) {
        p = head;
        do {
            q = p;
            p = p->next;
            delete q;
        } while (p != head);
        head = NULL;
    }
}

template <typename T>
void sglklist_print_cycle(T *head)
{
    T *p;

    if (head) {
        p = head;
        do {
            cout << p->key << " ";
            p = p->next;
        } while (p != head);
    }
    cout << endl;
}

/*
 * For single linked list with head.
 */
template <typename T>
void sglklist_init_head(T *&head)
{
    head = new T;
    assert(head);
    head->next = NULL;
}

template <typename T, typename K>
void sglklist_create_head(T *&head)
{
    T **p;
    int n;

    sglklist_init_head(head);
    p = &head->next;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->next = NULL;
        p = &(*p)->next;
    }
}

template <typename T>
void sglklist_destory_head(T *&head)
{
    T *p;

    while (head->next) {
        p = head->next;
        head->next = head->next->next;
        delete p;
    }
    delete head;
    head = NULL;
}

template <typename T>
void sglklist_print_head(T *head)
{
    T *p = head->next;

    while (p) {
        cout << p->key << " ";
        p = p->next;
    }
    cout << endl;
}

/*
 * For single linked list with head and cycle.
 */
template <typename T>
void sglklist_init_head_cycle(T *&head)
{
    head = new T;
    assert(head);
    head->next = head;
}

template <typename T, typename K>
void sglklist_create_head_cycle(T *&head)
{
    T **p;
    int n;

    sglklist_init_head_cycle(head);
    p = &head->next;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->next = head;
        p = &(*p)->next;
    }
}

template <typename T>
void sglklist_destory_head_cycle(T *&head)
{
    T *p, *q;

    p = head->next;
    while (p != head) {
        q = p;
        p = p->next;
        delete q;
    }
    delete head;
    head = NULL;
}

template <typename T>
void sglklist_print_head_cycle(T *head)
{
    T *p = head->next;

    while (p != head) {
        cout << p->key << " ";
        p = p->next;
    }
    cout << endl;
}

#endif

